/**
 * 插入排序
 * 算法思路：假定数组第一个元素已排序，取已排序的数组元素集的下一个元素作为游标，从右往左，找到第一个小于等于这个元素的数，在其后插入这个游标，不断循环此操作，直到最有一个元素，最终就会得到排序好的数组
 * 算法时间复杂度：O(n2) 
 * 算法空间复杂度：O(1)
 */

//  @fixme  插入排序目前怎么写都还是有问题
export default function (pararr) {
    if (!Array.isArray(pararr) || pararr.length < 2) {
        return;
    }
    let arr = [].concat(pararr);

    for (let i = 1; i <= arr.length - 1; i++) {
        for (let j = i - 1; j >= 0; j--) {
            if (arr[j] <= arr[i]) {
                //插入到找到的第一个小于等于自己的数后面，如果上来第一个数就是，则不需要继续比较了，也不需要移动元素，直接进入下一轮
                if(i!=j+1) arr.splice(j + 1, 0, arr.splice(i, 1)[0]);
                break;
            }
        }
    }
    return arr;
}